//
// Created by QU on 25-3-16.
//

#include <algorithm>
#include <functional>
#include <inttypes.h>
#include <iostream>
#include <queue>
#include <random>

using namespace std;

class PriorityQueue {
public:
    using Comparator = function<bool(int, int)>;

public:
    PriorityQueue(int cap = 20, const Comparator& comp = std::greater<int>())
        : capacity_(cap)
        , comp_(comp)
        , size_(0)
    {
        queue_ = new int[capacity_];
    }

    PriorityQueue(const Comparator& comp)
        : capacity_(20)
        , comp_(comp)
        , size_(0)
    {
        queue_ = new int[capacity_];
    }

    ~PriorityQueue()
    {
        delete[] queue_;
        queue_ = nullptr;
    }

public:
    void push(int value)
    {
        if (size_ == capacity_) {
            int* p = new int[capacity_ * 2];
            std::memcpy(p, queue_, capacity_ * sizeof(int));
            delete[] queue_;
            queue_ = p;
            capacity_ *= 2;
        }

        if (size_ == 0) {
            // 只有一个元素, 不用上浮调整
            queue_[0] = value;
        } else {
            // 多个元素, 需要上浮调整
            shiftup(size_, value);
        }
        size_++;
    }

    void pop()
    {
        if (size_ == 0) {
            throw std::out_of_range("The queue is empty.");
        }

        size_--;

        if (size_ > 0) {
            // 删除了元素，还有元素需要下沉调整
            shiftdown(0, queue_[size_]);
        }
    }

    int top() const
    {
        if (size_ == 0) {
            throw std::out_of_range("The queue is empty.");
        }
        return queue_[0];
    }

    int size() const
    {
        return size_;
    }

    bool empty() const
    {
        return size_ == 0;
    }

private:
    void shiftup(int pos, int val)
    {
        // 最多计算到根节点
        while (pos > 0) {
            int parent_pos = (pos - 1) / 2;

            if (comp_(val, queue_[parent_pos])) {
                queue_[pos] = queue_[parent_pos];
                pos = parent_pos;
            } else {
                break;
            }
        }
        queue_[pos] = val;
    }

    void shiftdown(int pos, int val) // O(logn) O(1)
    {
        // pos下沉不能超过最后一个有孩子的节点
        while (pos <= ((size_ - 1) - 1) / 2) {
            int child_pos = pos * 2 + 1; // 左孩子这里一定是有的, 上面的条件是至少有孩子
            if (child_pos + 1 < size_ && comp_(queue_[child_pos + 1], queue_[child_pos])) {
                // 有右孩子， 右大于左
                child_pos++; // 左变成右
            }
            // 已经确定了放在左孩子还是右孩子，是否下沉
            if (comp_(queue_[child_pos], val)) {
                queue_[pos] = queue_[child_pos];
                pos = child_pos;
            } else {
                break; // 已经满足
            }
        }
        queue_[pos] = val;
    }

private:
    int* queue_;
    int size_;
    int capacity_;

    Comparator comp_;
};

int main(int argc, char** argv)
{
    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_int_distribution<int> dis(0, 100);

    static constexpr int MAX_ARRAY_SIZE = 50;
    const auto arr = new int[MAX_ARRAY_SIZE];

    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        arr[i] = dis(engine);
    }

    std::for_each(arr, arr + MAX_ARRAY_SIZE, [](const int a) { std::cout << a << ' '; });

    std::cout << std::endl;

    // PriorityQueue pq(std::less<int>());
    // 当你使用圆括号()初始化对象时，可能会触发"最令人烦恼的解析"（Most Vexing Parse）问题。
    // 这行代码实际上被编译器解释为： 声明一个名为pq的函数,该函数接收一个参数（类型是返回std::less<int>的无参函数指针）,返回类型为PriorityQueue

    PriorityQueue pq { std::less<int>() };
    // PriorityQueue pq1((std::less<int>()));       // C++11 之前的解决方式

    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        pq.push(arr[i]);
    }

    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }

    // 释放动态分配的内存
    delete[] arr;

    return 0;
}